package com.cuz.hot100;

import com.cuz.hot100.datastruck.ListNode;

public class Q25ReverseKGroup {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        ListNode listNode = solution3(n1, 2);
        listNode.print();
    }

    public static ListNode reverseLinkList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode cur = head;
        ListNode post = cur.next;
        cur.next = null;
        cur = post;
        while (cur != null) {
            post = cur.next;
            cur.next = preHead.next;
            preHead.next = cur;
            cur = post;
        }
        return preHead.next;
    }

    public static ListNode solution3(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode after = head;
        ListNode before = after;
        for (int i = 0; i < k - 1; i++) {
            before = before.next;
            if (before == null) {
                return head;
            }
        }
        ListNode pre = preHead;
        ListNode next = before.next;
        do {
            before.next = null;
            pre.next = reverseLinkList(after);
            after.next = next;
            pre = after;
            after = next;
            before = after;
            for (int i = 0; i < k - 1; i++) {
                if (before == null) {
                    return preHead.next;
                }
                before = before.next;
            }
            if (before == null) {
                return preHead.next;
            }
            next = before.next;
        } while (next != null);
        pre.next = reverseLinkList(after);
        return preHead.next;
    }




}
